The present invention relates in general to data processing networks, and in particular to Available Bit Rate (ABR) data flow control in Asynchronous Transfer Mode (ATM) networks.
In early data communication networks, data flow control and error detection/recovery were typically performed at each intermediate node or system on the path between the source and destination systems. Such hop-by-hop operations were thought to be necessary to deal with data lost or corrupted as a result of using the then available high error rate data transmission technology and media.
Data transmission technology and media have improved over time, allowing data communications networks to evolve into systems in which flow control and error detection/recovery can become primarily the responsibility of nodes at the end points of a network data path. Minimizing packet processing operations (and the time required to perform such operations) at intermediate nodes reduces the time required to move the data from source to destination, that is, increases system throughput.
Asynchronous Transfer Mode or ATM technology is an increasingly pervasive example of a technology in which flow control and error detection/recovery are typically performed primarily at end nodes on a data path. In ATM systems, all data is transported in relatively short fixed length cells. Standard ATM cells have a five byte header, which carries cell control and routing information, and a forty-eight byte payload, which normally carries actual user data. The advantage of using fixed length cells is that such cells can be switched at extremely high speeds by special purpose hardware switches within the ATM network.
While the ATM cell structure may be standard, the data transported in such cells may represent different types of information having different, sometimes inconsistent characteristics and transport requirements. Transported data may represent computer data or audio information or image information. Examples of audio information include human speech or music. Examples of image information include xe2x80x9clivexe2x80x9d video or photographs or graphic or medical images.
Where the data being transported represents audio or video information, a loss of a certain amount of the data during transmission generally can be tolerated before the quality of the reconstructed audio or video information is noticeably degraded. However, certain kinds of such data, such as live video signals or speech, cannot be excessively delayed or subject to cell-to-cell end-to-end variations in transit time (that is, be subject to jitter) without causing a significant loss of quality of the reconstructed audio or video information. In contrast, a certain level of transmission delay or jitter is tolerable for computer data while loss or corruption of such data is generally intolerable.
Data which must be delivered with low tolerances on delay or jitter is characterized as real-time (RT) data. Data which is delay-tolerant is characterized as non-real-time (NRT) data. In most cases, RT data is loss-tolerant while NRT data is loss-intolerant.
Any data communications network, including an ATM network, has a limited capacity (bandwidth) available for the transport of user data. The goal of a network designer or administrator is to consistently use as much of that bandwidth as possible while continuing to satisfy loss and/or delay requirements for the different kinds of data that are transported. Generically, loss and delay requirements are referred to as Quality of Service or QOS requirements.
In an ATM network, a connection is normally set up each time a source node wishes to send data to a destination node in the network. The connection setup includes the selection of a route or path through the network and the establishment of service parameters and QOS guarantees for the duration of the connection. Multiple connections between source-destination pairs can concurrently use the same physical links in the network. To accommodate the different service requirements of different kinds of traffic in an ATM network, different classes of ATM traffic have been defined. The defined classes of interest are CBR (Constant Bit Rate), VBR (Variable Bit Rate) and ABR (Available Bit Rate). A fourth defined class of ATM traffic, Unspecified Bit Rate or UBR, is of no interest. UBR traffic has the lowest priority of any ATM traffic and is allocated only whatever network bandwidth is left over after the requirements of higher priority (CBR, VBR and ABR) classes of ATM traffic are satisfied.
CBR traffic is traffic that needs to be transmitted at a specified, substantially constant bit rate. Examples of CBR traffic include real-time audio or video traffic or an ATM network connection emulating a standard T1 (1.544 Mbit/s) line. CBR traffic is delay and jitter intolerant. During set up of a CBR connection, a Peak Cell Rate (PCR) must be negotiated to define the maximum rate at which data can be transported without creating a significant risk of cell loss. Data is typically then transmitted at the negotiated PCR rate. If an attempt in made to transmit traffic at a rate exceeding the PCR, the excess traffic may be discarded by the network.
VBR traffic includes two subclasses of trafficxe2x80x94VBR real-time (VBR-RT) and VBR non-real-time (VBR-NRT. VBR-RT traffic is traffic which may be generated at varying rates (that is, be bursty) while still requiring tight limits on acceptable limits of cell jitter. Examples of VBR-RT traffic include video signals generated by a variable-rate codec or aggregated voice traffic with silence removal. VBR-NRT traffic is traffic which may be bursty but which is more delay tolerant than VBR-RT traffic. An example of VBR-NRT traffic includes traffic resulting from transaction processing, such as credit verification or other point-of-sale operations.
For each VBR connection to be set up, a Peak Cell Rate, a Sustained Cell Rate (SCR) and a jitter tolerance value must be negotiated. The negotiated SCR represents the average throughput to be permitted over the connection. While traffic may be accepted from a VBR source at rates exceeding the negotiated SCR for short periods of time (as long as the excess rates do not exceed the negotiated PCR), the rate at which traffic will subsequently be accepted from the same source must be reduced below the SCR sufficiently to maintain the negotiated SCR over a longer period of time. To assure that the SCR parameter can be observed over a relatively long period of time, still another parameter, a burst tolerance, must be established when the connection is being set up. Burst tolerance defines how long a VBR connection will be allowed to accept traffic at rates greater than SCR before the traffic rate is reduced below SCR to maintain an overall throughput not exceeding SCR
During these periods of reduced traffic activity and perhaps at other times during network operation, a significant amount of network bandwidth may be unused or idle. The ABR traffic class has been defined in an effort to exploit the availability of idle network bandwidth. ABR traffic is intended to make optimum use of what might otherwise be unused network bandwidth while utilizing traffic management techniques to monitor actual or incipient network congestion which might, if not taken into account, lead to unacceptable cell loss during transmission attempts.
The setup of an ABR connection requires negotiation of the same kind of PCR parameter that exists for a VBR connection. The PCR parameter serves the same purpose for both kinds of connections; namely, to limit the maximum rate at which traffic will be accepted for transmission over the connection. No effort is made to negotiate jitter or burst tolerances for ABR traffic. Instead, the ABR source and the network negotiate a Minimum Cell Rate (MCR) parameter representing the minimum amount of connection bandwidth that will always be available to the ABR traffic source. Generally, the MCR parameter represents the minimum transmission rate which must be available if the ABR traffic source or application is to stay alive, i.e., continue to execute.
For CBR and VBR connections in an ATM network, no effort is made to dynamically control congestion (network traffic loads) from within the network. If, however, the goal is to achieve maximum utilization of what would otherwise be idle network bandwidth, it makes sense to attempt to dynamically control congestion through the use of closed-loop congestion management techniques. Such techniques monitor network traffic and provide feedback to a traffic source to permit that source to adjust the rate at which traffic is made available to the network. Knowing that source traffic rates can be adjusted, a more aggressive approach to allocating bandwidth to ABR traffic may be implemented.
A more sophisticated feedback mechanism, identified as Explicit Rate Marking (ERM), allows the intermediate switches to play a larger role in the control of network congestion. Generally speaking, an ERM switch monitors the state of the network at the switch by making specific measurements of network operating parameters. If the measurements indicate that additional bandwidth is available for a specific ABR connection, the switch calculates a new explicit rate (ER) for the ABR traffic that it can accept from the source. The calculated, new explicit rate is written into RM cells received from the associated source for eventual delivery to the source. The source station responds by increasing the source transmission rate to make better use of the idle bandwidth.
Different algorithms are used in the prior art to generate ER values. However, these do not offer delay guarantees. That is, the present art does not bound queuing delays. Thus, there is a need in the art for an improved ER mechanism and apparatus that ensures that queuing delays are smaller than a predetermined maximum value.
The present invention addresses the previously mentioned needs by providing a method and apparatus for generating ER values that ensure that a predetermined maximum queue length is not exceeded. A closed-loop feedback system is implemented based on ERM in which ER values are generated based on the concept of a critically damped system. A next explicit rate to be transmitted to an ATM ABR source in order to instruct the source how to adjust its traffic rate is generated using an algorithm that seeks to damp the ER towards a time-dependent share value.
The ATM device seeking to control the source traffic rate first determines the actual cell rate for each active ABR connection. It does so by monitoring the cell traffic from the source during a preselected interval of time. The actual cell rate is simply computed as the number of cells from the source passing through the device per unit time. However, the actual cell rate so obtained is the actual cell rate of the source at time that is earlier than the time at which the cells are counted by an amount equal to the travel time between the source and the controlling ATM device. The controlling ATM device then determines a share value according to an algorithm using the aggregate of the actual cell rates determined for each connected ABR source.
The controlling ATM device then determines a present ER value using this share value and the two previous ER values it sent to the source. The present ER value is determined by a rule such that the sequence of ER values issued in succeeding RM cells is damped toward the share value.
After the present ER value is determined, the controlling ATM device transmits it to the source. The present ER value is incorporated into the ER field of a Backward Resource Management (BRM) cell. The source receiving the BRM adjusts its actual cell rate to be equal to, or smaller than, the ER encapsulated in the BRM. Note, however, that the new actual cell rate so determined corresponds to an ER value that was transmitted to the source one transit time earlier. That is, the xe2x80x9cpresentxe2x80x9d time at the source is advanced by a transit period from the time corresponding to the ER value received by the source.